package com.leet.code.lcof;

import java.util.LinkedList;

public class Code49 {

    public static void main(String[] args) {
//
//        for (int i = 8; i < 1000; i++) {
//
//            LinkedList<Integer> list = new LinkedList<>();
//            int n = i;
//            while (n % 5 == 0) {
//                n = n / 5;
//                list.add(5);
//            }
//
//            while (n % 3 == 0) {
//                n = n / 3;
//                list.add(3);
//            }
//            while (n % 2 == 0) {
//                n = n / 2;
//                list.add(2);
//            }
//            if (n == 1) {
//
//                StringBuilder sb = new StringBuilder(String.valueOf(i)).append(" ");
//                for (Integer j : list) {
//                    sb.append(j).append("*");
//                }
//                sb.append("\b");
//                System.out.println(sb.toString());
////                System.out.print(i + ",");
//            }
//        }
        int c = new Code49().nthUglyNumber(10);
        System.out.println(c);
    }


    public int nthUglyNumber(int n) {

        int[] is = new int[n];
        is[0] = 1;
        int s2 = 2, s3 = 3, s5 = 5;
        int a = 0, b = 0, c = 0;
        for (int i = 1; i < n; i++) {
            is[i] = Math.min(s2, Math.min(s3, s5));
            if (s2 == is[i]) {
                a++;
                s2 = 2 * is[a];
            }
            if (s3 == is[i]) {
                b++;
                s3 = 3 * is[b];
            }
            if (s5 == is[i]) {
                c++;
                s5 = 5 * is[c];
            }

        }

        return is[n - 1];
    }


    public int pow(int d, int p) {
        if (p == 0) {
            return 1;
        }
        if (d == 2) {
            return 2 << (p - 1);
        }
        while (p > 1) {
            d = d * d;
            p--;
        }
        return d;
    }


}
/*

2   2*1
3   3*1

4   2*2
5   5*1
6   3*2
8   2*2*2
9   3*3
10  5*2
12  3*2*2
15  5*3
16  2*2*2*2
18  3*3*2
20  5*2*2
24  3*2*2*2
25  5*5
27  3*3*3
30  5*3*2
32  2*2*2*2*2
36  3*3*2*2




*/